# 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
#
#  示例 1:
#
#  输入: [3,2,1,5,6,4] 和 k = 2
# 输出: 5
#
#
#  示例 2:
#
#  输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
# 输出: 4
#
#  说明:
#
#  你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
#  Related Topics 堆 分治算法
#  👍 675 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
from typing import List


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:

        def median3(arr, left, right):
            center = (left + right) // 2
            if arr[left] > arr[center]:
                arr[left], arr[center] = arr[center], arr[left]
            if arr[left] > arr[right]:
                arr[left], arr[right] = arr[right], arr[left]
            if arr[center] > arr[right]:
                arr[center], arr[right] = arr[right], arr[center]

            pivot = arr[center]
            arr[center], arr[left] = arr[left], arr[center]
            return pivot

        def partition(arr, left, right):
            low = left
            high = right

            # 用中值做优化，否则一直用arr[left] 作为基准数 ，对于极端情况，非常慢
            pivot = median3(arr, left, right)
            while low != high:

                # 内层两个while循环顺序不能变，因为 如果先移动 左指针，最后左指针停下位置的数字必然比基准数大，
                # 最后和基准数交换就是错误的，所以让右指针先动，停留的数字就比基准数小，可以正确交换
                while arr[high] > pivot and low < high:
                    high -= 1

                # 后半部出现的比基准数小的数字赋值给 arr[low] ,此时 low指针没动，可以被覆盖

                arr[low] = arr[high]

                while arr[low] <= pivot and low < high:
                    low += 1

                arr[high] = arr[low]

            arr[low] = pivot
            return low

        def quickSort(nums, left, right):
            index = partition(nums, left, right)
            quickSort(nums, left, index - 1)
            quickSort(nums, index + 1, right)

        def quickSelect(nums, left, right, index):
            q = partition(nums, left, right)
            if q == index:
                return nums[q]
            else:
                if index > q:
                    return quickSelect(nums, q + 1, right, index)
                else:
                    return quickSelect(nums, left, q - 1, index)

        return quickSelect(nums, 0, len(nums) - 1, len(nums) - k)


# leetcode submit region end(Prohibit modification and deletion)

print(Solution().findKthLargest([3, 2, 1, 5, 6, 4], 2))
